#include "leecode.h"
#include "limits.h"

class Solution {
public:
    enum CanReach {
      NotCalculated,
      Reached,
      CannnotReach,
    };
    bool canJump(vector<int>& nums) {
      int len = nums.size();
      if(len == 1)
        return true;
      else if(nums[0] == 0)
        return false; 
      
      can_reach_ = new int[len];
      memset(can_reach_, 0, len*4);
      can_reach_[0] = Reached;
      can_reach_[1] = Reached;
      bool ret = (canJumpImpl(nums, len) == Reached);
      delete [] can_reach_;
      return ret;
    }

    int canJumpImpl(vector<int>& nums, int len) {
      if(can_reach_[len-1] != NotCalculated)
        return (CanReach)can_reach_[len-1];

      for(int i = len -2; i >= 0; i--) {
        if((nums[i] >= len -i -1) && (canJumpImpl(nums, i+1) == Reached)) {
          can_reach_[len-1] = Reached;
          return Reached;
        }
      }
      can_reach_[len-1] = CannnotReach;
      return CannnotReach;
    }
    int* can_reach_ = nullptr;
};

TEST(canJump, canJump) {
  GTEST_SKIP();
  vector<int> v1{2,3,1,1,4};
  EXPECT_TRUE(Solution().canJump(v1));

  vector<int> v2{3,2,1,0,4};
  EXPECT_FALSE(Solution().canJump(v2));

  // vector<int> v3{3, 2, 1};
  // EXPECT_EQ(Solution().jump(v3), 1);
}
